import copy
import functools

class Solution(object):
    def encode(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        DP = [[(i, j) for j in range(n)] for i in range(n)]
        result_DP = [['' for j in range(i)] + [s[i: j + 1] for j in range(i, n)] for i in range(n)]
        len_DP = [[j - i + 1 if j >= i else 0 for j in range(n)] for i in range(n)]

        def cal(i, k, j):
            base = (j - i + 1) // (k - i + 1)
            if 2 + len(str(base)) < j - k:
                len_DP[i][j] = 2 + len(str(base)) + k - i + 1
                result_DP[i][j] = str(base) + '[' + s[i: k + 1] + ']'

        for i in range(n - 1):
            for j in range(i, n):
                for k in range(i, j):
                    if s[DP[i][k][0]: DP[i][k][1] + 1] == s[k + 1:j + 1]:
                        DP[i][j] = DP[i][k]
                        cal(i, DP[i][k][1], j)
                        break
        for m in range(n):
            for i in range(n - m):
                j = i + m
                base = (j - i + 1) // (DP[i][j][1] - DP[i][j][0] + 1)
                if len(str(base)) + 2 + len_DP[i][DP[i][j][1]] < len_DP[i][j]:
                    len_DP[i][j] = len(str(base)) + 2 + len_DP[i][DP[i][j][1]]
                    result_DP[i][j] = str(base) + '[' + result_DP[i][DP[i][j][1]] + ']'
                for k in range(i, j):
                    if len_DP[i][j] > len_DP[i][k] + len_DP[k + 1][j]:
                        len_DP[i][j] = len_DP[i][k] + len_DP[k + 1][j]
                        result_DP[i][j] = result_DP[i][k] + result_DP[k + 1][j]
        return result_DP[0][-1]

data = Solution()
# s = "abbbabbbcabbbabbbc"
# print(data.encode(s))
s = "aabcccccddd"
print(data.encode(s))
s = "edaaaaaabbbbbbaaaaaabbbbbb"
print(data.encode(s))

